package com.example.leetcode.trainingcamp.week7.Thursday;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 *
 * <p>
 *
 * <p>为了让您更好地理解问题，以下面的二叉搜索树为例：
 *
 * <p>
 *
 * <p>来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Offer36 {

    private final Node head = new Node(-1);

    private Node tail = head;

    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        reverse(root);
        Node right = head.right;
        tail.right = right;
        right.left = tail;
        return right;
    }

    public void reverse(Node root){
        if (root == null ) return;
        reverse(root.left);
        Node right = root.right;
        tail.right = root;
        root.left = tail;
        tail = root;
        reverse(right);
    }
}

class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}









